Godsil type identities of the multi-variate independence polynomials of graphs from heaps theory.

Abstract

Given a simple graph G, one can associate a monoid called Cartier–Foata monoid of G (denote it as CF(G)). It is also called trace monoid or partially commutative monoid of G in the literature. Viennot introduced “heaps of pieces” that give geometric interpretations of elements of CF(G). One can show that the monoid of heaps of pieces in the vertices of G with the concurrency relation determined by G is equivalent to CF(G). The fundamental result of Viennot’s general theory of heaps is the inversion lemma which gives a closed formula for the generating function of heaps with all maximal pieces in some fixed subset.

In this talk, we will see how to get some identities for the multi-variate independence polynomial of G from the perspective of heaps theory. Using the inversion formula and the combinatorics of partially commutative monoid, we show how the multi-variate version of Godsil type identity and the fundamental identity can be obtained from weight preserving bijections. This is joint work with Deniz Kus and Kartik Singh.

Reference: https://arxiv.org/abs/2209.08029